Skip to main content

​
FNP - Data Structures - LSEQ CRDT Identifiers

​
Summary (Explain Like I’m 5)

Imagine you and 100 colleagues editing a document at the same exact moment, all inserting at position 0. What’s the order? LSEQ solves this by giving every character a unique ID that’s created locally before the server sees it:
  • You insert “H” → ID = [500, from_you, timestamp]
  • Colleague inserts “e” → ID = [501, from_them, timestamp]
  • Both created simultaneously but deterministically ordered: 500 < 501
Each character keeps its position forever, even if thousands of other characters are added around it.

​
Technical Deep Dive

LSEQ (LogootSplit) is a Conflict-free Replicated Data Type using variable-length position identifiers to maintain deterministic document order without coordination. Identifier Structure: 
ID = [⟨digit₁, site₁, counter₁⟩, ⟨digit₂, site₂, counter₂⟩, ..., ⟨digitₙ, siteₙ, counterₙ⟩]

where:
  digit_i ∈ [0, 2^54)     - Position value at level i
  site_i ∈ [0, 2^32)      - Replica ID (breaks ties)
  counter_i ∈ ℕ           - Lamport clock at replica (breaks identical digit+site)
Ordering Rules (Lexicographic): For A = [d₁^A, d₂^A, …] and B = [d₁^B, d₂^B, …]: 
A < B iff ∃i: (
  ∀j < i: A[j] = B[j]
  AND (d_i^A < d_i^B OR (d_i^A = d_i^B AND site_i^A < site_i^B) OR ...)
)
Insertion Algorithm (Simplified Midpoint Strategy): 
Insert(left_id, right_id, site_id, counter):
  1. Find common prefix length: k = max{i : left[0..i] = right[0..i]}

  2. Extract divergence:
     left_digit = left[k].digit OR 0
     right_digit = right[k].digit OR 2^54-1

  3. If gap > 1:
       new_digit = (left_digit + right_digit) / 2
       new_id = [left[0..k-1], ⟨new_digit, site_id, counter⟩]
     Else:
       # Need next level (depth doubling)
       new_id = [left[0..k], ⟨0, site_id, counter⟩]

  Return new_id
Space Complexity: O(log N) depth for N insertions (binary tree structure). Conflict Resolution: Multiple concurrent inserts at same position get unique (site_id, counter) pairs → both preserved deterministically. Under M²-ORE Encryption: 
Enc(LSEQ_identifier, pk_m2ore):
  for each ⟨digit_i, site_i, counter_i⟩:
    encrypted_digit_i = M2ORE.Enc(pk_m2ore, digit_i)
    keep site_i, counter_i in plaintext (metadata)
  return [encrypted_digit_1, encrypted_digit_2, ..., encrypted_digit_n]
Critical Property: Plaintext order preserved in ciphertext!
  • Enc_id_1 < Enc_id_2 ⟺ id_1 < id_2 (order preserved in ciphertext domain)

​
Mermaid Diagrams

​
Key Terms

  • LSEQ → LogootSplit; CRDT using variable-length identifiers
  • CRDT → Conflict-free Replicated Data Type; commutative, associative, idempotent merge
  • Lexicographic Order → Dictionary order; compare element-by-element left-to-right
  • Depth Doubling → When gap between consecutive digits exhausted, recurse to next level
  • Site ID → Unique replica identifier; breaks ties when digits and counters match
  • Lamport Clock → Monotonic counter incremented on each local operation; breaks duplicate (digit, site)
  • Concurrent Conflicts → Multiple simultaneous edits; LSEQ provides deterministic resolution
  • Position Stability → Character position never changes; enables efficient caching and offline editing

​
Q/A

Q: How do 100 people editing simultaneously at position 0 not create chaos? A: Each person generates their own unique ID locally based on their replica ID and Lamport clock. Position 0 becomes many unique IDs (500, 501, 502, …) that are deterministically ordered. Server merges by comparing encrypted identifiers using M²-ORE. Q: What prevents ID explosion? Don’t IDs get really long? A: IDs grow as O(log N) depth for N insertions. Even after 1 million insertions, average depth is only ~20 tuples. Most characters have 1-3 tuples. Typical LSEQ identifier: [⟨500, site=1, counter=5⟩, ⟨250, site=2, counter=3⟩] - only 2 levels deep. Q: Why include site_id and counter if digit uniquely identifies position? A: Multiple replicas might generate identical digits simultaneously. Example: Alice generates digit=500 at replica 1, Bob generates digit=500 at replica 2. Tiebreaker: compare (site_id, counter). Alice_site < Bob_site → Alice’s insertion comes first. Q: How are IDs encrypted while preserving ordering? A: Each digit is independently encrypted with M²-ORE, creating an encrypted identifier. The critical property: if digit₁ < digit₂, then Enc(digit₁) < Enc(digit₂) in the encrypted domain. Server compares encrypted identifiers directly. Q: What happens if someone tries to reorder identifiers by tampering with site_id or counter? A: LSEQ identifiers are deterministically generated and immutable. Tampering is detected as invalid operations. Halo2 proofs verify that the identifier was correctly generated; invalid IDs are rejected by the server.

​
Example / Analogy

Library Shelf Analogy: You and friends are organizing a shared library remotely:
  • Without LSEQ: “Put book at position 5” - if everyone puts books at position 5 simultaneously, conflict!
  • With LSEQ: Each book gets a unique barcode at the moment you decide to shelve it:
    • Your book: barcode 500.001 (your ID is 001)
    • Friend’s book: barcode 500.002 (their ID is 002)
    • Both meant to go at “position 5” but get unique, ordered barcodes
    • Shelf auto-sorts by barcode: both books end up in right order with no conflict
Real-world FNP Scenario: You and 3 colleagues are writing a proposal together, all starting to write the introduction simultaneously from blank page:
  1. Each writes locally with M²-ORE encryption
  2. LSEQ gives each character a unique ID created before sending to server
  3. Your characters: [⟨[500…], site=1, clk=1⟩, ⟨[501…], site=1, clk=2⟩, …]
  4. Colleague 2’s characters: [⟨[500…], site=2, clk=1⟩, …]
  5. Server merges deterministically using M²-ORE comparison
  6. Everyone sees identical order - no conflicts, no “who goes first?”
Cross-References: System Overview, M²-ORE Encryption, FNP Protocol Flow, Halo2 Circuits Category: Data Structures | Consensus | CRDT | Protocol Difficulty: Intermediate ⭐⭐⭐ Updated: 2025-11-28